{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Decode String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #recursion #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #递归 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: decodeString"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #字符串解码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个经过编码的字符串，返回它解码后的字符串。</p>\n",
    "\n",
    "<p>编码规则为: <code>k[encoded_string]</code>，表示其中方括号内部的 <code>encoded_string</code> 正好重复 <code>k</code> 次。注意 <code>k</code> 保证为正整数。</p>\n",
    "\n",
    "<p>你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。</p>\n",
    "\n",
    "<p>此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 <code>k</code> ，例如不会出现像&nbsp;<code>3a</code>&nbsp;或&nbsp;<code>2[4]</code>&nbsp;的输入。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"3[a]2[bc]\"\n",
    "<strong>输出：</strong>\"aaabcbc\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"3[a2[c]]\"\n",
    "<strong>输出：</strong>\"accaccacc\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"2[abc]3[cd]ef\"\n",
    "<strong>输出：</strong>\"abcabccdcdcdef\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc3[cd]xyz\"\n",
    "<strong>输出：</strong>\"abccdcdcdxyz\"\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 30</code></li>\n",
    "\t<li><meta charset=\"UTF-8\" /><code>s</code>&nbsp;由小写英文字母、数字和方括号<meta charset=\"UTF-8\" />&nbsp;<code>'[]'</code> 组成</li>\n",
    "\t<li><code>s</code>&nbsp;保证是一个&nbsp;<strong>有效</strong>&nbsp;的输入。</li>\n",
    "\t<li><code>s</code>&nbsp;中所有整数的取值范围为<meta charset=\"UTF-8\" />&nbsp;<code>[1, 300]</code>&nbsp;</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [decode-string](https://leetcode.cn/problems/decode-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [decode-string](https://leetcode.cn/problems/decode-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"3[a]2[bc]\"', '\"3[a2[c]]\"', '\"2[abc]3[cd]ef\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        num_stack = list()\n",
    "        stack = list()\n",
    "        for ch in s:\n",
    "            if ch >=\"0\" and ch <=\"9\":\n",
    "                num_stack.append(ch)\n",
    "            elif ch == '[':\n",
    "                stack.append(ch) \n",
    "                # pop num\n",
    "                nums = list()\n",
    "                while num_stack:\n",
    "                    if type(num_stack[-1]) is int:\n",
    "                        break\n",
    "                    else:\n",
    "                        nums.insert(0,num_stack.pop())\n",
    "                num_stack.append(int(\"\".join(nums)))\n",
    "            \n",
    "            elif ch >='a' and ch<='z':\n",
    "                stack.append(ch)\n",
    "            else:\n",
    "                #  ch == ']'\n",
    "                chars = list()\n",
    "                while stack:\n",
    "                    top = stack.pop()\n",
    "                    if top !='[':\n",
    "                        chars.insert(0, top)\n",
    "                    else:\n",
    "                        break\n",
    "                \n",
    "                stack.append(\"\".join(num_stack.pop()*chars))\n",
    "        return \"\".join(stack)\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        stack1 = []\n",
    "        stack2 = []\n",
    "        cur = 0\n",
    "        n = len(s)\n",
    "        ss = ''\n",
    "        while cur < n:\n",
    "            c = s[cur]\n",
    "            if ord(c) >= 48 and ord(c) <= 57:\n",
    "                start = cur\n",
    "                while ord(s[cur]) >= 48 and ord(s[cur]) <= 57:\n",
    "                    cur += 1\n",
    "                stack1.append(int(s[start:cur]))\n",
    "                stack2.append(ss)\n",
    "                ss = ''\n",
    "            elif c == ']':\n",
    "                ss = stack2.pop() + stack1.pop() * ss\n",
    "            else:\n",
    "                ss += s[cur]\n",
    "            cur += 1\n",
    "        return ss"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        def gen_string1(rep,sub_str):\n",
    "            temp =''\n",
    "            for i in range(0,rep):\n",
    "                temp+=(sub_str)\n",
    "            return temp\n",
    "\n",
    "        def gen_string_main(new_str):\n",
    "            rep = 0\n",
    "            ptn_start =len(new_str)-1\n",
    "            while new_str[ptn_start]!='[':\n",
    "                 ptn_start -=1\n",
    "            rep_start = ptn_start -1\n",
    "            while ord('0')<= ord(new_str[rep_start] )<=ord('9') :\n",
    "                rep_start-=1\n",
    "            rep = int(new_str[rep_start+1:ptn_start])\n",
    "            ptn_end = ptn_start+1\n",
    "            while new_str[ptn_end]!=']':\n",
    "                  ptn_end+=1\n",
    "            temp1 = new_str[0:rep_start+1]\n",
    "            temp2 = gen_string1(rep,new_str[ptn_start+1:ptn_end])\n",
    "            temp3 = new_str[ptn_end+1:len(new_str)]\n",
    "            return temp1 + temp2 + temp3\n",
    "\n",
    "        while '[' in s or ']' in s:\n",
    "          s =   gen_string_main(s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        temp_res = []\n",
    "        cur_str = ''\n",
    "        cur_num = 0\n",
    "        for char in s:\n",
    "            if char == '[':\n",
    "                temp_res.append(cur_str)\n",
    "                temp_res.append(cur_num)\n",
    "                cur_str = ''\n",
    "                cur_num = 0\n",
    "            elif char == ']':\n",
    "                pre_num = temp_res.pop()\n",
    "                pre_str = temp_res.pop()\n",
    "                cur_str = pre_str + pre_num * cur_str\n",
    "            elif char.isdigit():\n",
    "                cur_num = cur_num * 10 + int(char)\n",
    "            else:\n",
    "                cur_str += char\n",
    "                \n",
    "        return cur_str"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        n = len(s)\n",
    "        stack = []\n",
    "        for i in range(n):\n",
    "            if s[i]!=\"]\":\n",
    "                stack.append(s[i])\n",
    "            else:\n",
    "                temp = \"\"\n",
    "                t = stack.pop()\n",
    "                while(t!='['):\n",
    "                    temp = t + temp\n",
    "                    t = stack.pop()\n",
    "                count =\"\"\n",
    "                while(stack and stack[-1].isdigit()):\n",
    "                    count = stack.pop() + count\n",
    "                count = int(count)\n",
    "                temp = temp*count\n",
    "                stack.append(temp)\n",
    "        res = \"\".join(stack)\n",
    "        return res\n",
    "        \n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack = []\n",
    "        aws = ''\n",
    "        for char in s:\n",
    "            if char != ']':\n",
    "                stack.append(char)\n",
    "                print(stack)\n",
    "            if char == ']':\n",
    "                res = ''\n",
    "                for i in range(len(stack)):\n",
    "                    temp = stack.pop()\n",
    "                    print('temp:', temp)\n",
    "                    if temp != '[':\n",
    "                        res += temp\n",
    "                    if temp == '[':\n",
    "                        times = ''\n",
    "                        print('len(stack)', len(stack), stack)\n",
    "                        for _ in range(len(stack)):\n",
    "                            time = stack.pop()\n",
    "                            if time.isdigit():\n",
    "                                times += time\n",
    "                            else:\n",
    "                                stack.append(time)\n",
    "                                break\n",
    "                            \n",
    "                        times = times[::-1]\n",
    "                        res *= int(times)\n",
    "                        # res = res[::-1]\n",
    "                        stack.append(res)\n",
    "                        break\n",
    "                print(\"stack\",stack)\n",
    "                \n",
    "\n",
    "        return ''.join([s[::-1] for s in stack])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        multi = 0\n",
    "        res = ''\n",
    "        stack = []\n",
    "        for ch in s:\n",
    "            if ch == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = '', 0\n",
    "            elif ch == ']':\n",
    "                cur_mult, cur_res = stack.pop()\n",
    "                res = cur_res + cur_mult * res\n",
    "            elif '0' <= ch <= '9':\n",
    "                multi = multi * 10 + int(ch)\n",
    "            else:\n",
    "                res += ch\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                multi, res = 0, \"\"\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi*res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi*10 + int(c)\n",
    "            else:\n",
    "                res += c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        num = 0\n",
    "        res = \"\"\n",
    "        numStack = []\n",
    "        strStack = []\n",
    "        for i in s:\n",
    "            if i.isdigit():\n",
    "                num = num * 10 + int(i)\n",
    "            elif i == \"[\":\n",
    "                numStack.append(num)\n",
    "                strStack.append(res)\n",
    "                num, res = 0, \"\"\n",
    "            elif i == \"]\":\n",
    "                num = numStack.pop()\n",
    "                string = strStack.pop()\n",
    "                res = string + res * num \n",
    "                num = 0\n",
    "            else:\n",
    "                res += i\n",
    "        return res\n",
    "\n",
    "        # stack = []  # (str, int) 记录之前的字符串和括号外的上一个数字\n",
    "        # num = 0\n",
    "        # res = \"\"  # 实时记录当前可以提取出来的字符串\n",
    "        # for c in s:\n",
    "        #     if c.isdigit():\n",
    "        #         num = num * 10 + int(c)\n",
    "        #     elif c == \"[\":\n",
    "        #         stack.append((res, num))\n",
    "        #         res, num = \"\", 0\n",
    "        #     elif c == \"]\":\n",
    "        #         top = stack.pop()\n",
    "        #         res = top[0] + res * top[1]\n",
    "        #     else:\n",
    "        #         res += c\n",
    "        # return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        def f(m):\n",
    "            return int(m.group(1)) * m.group(2)\n",
    "        while '[' in s:\n",
    "            s = re.sub(r'(\\d+)\\[([A-Za-z]*)\\]',f,s)\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack=[]\n",
    "        n=len(s)\n",
    "        ans=''\n",
    "        sz={'1':1,\"2\":2,\"3\":3,\"4\":4,\"5\":5,\"6\":6,'7':7,'8':8,'9':9,'0':0}\n",
    "        i=0\n",
    "        while i <n:\n",
    "            if s[i] in sz:\n",
    "                co=0\n",
    "                while s[i]in sz:\n",
    "                    co=co*10+sz[s[i]]\n",
    "                    i+=1\n",
    "                stack.append(co)\n",
    "            elif s[i] == ']':\n",
    "                cur=''\n",
    "                while stack[-1]!='[':\n",
    "                    cur=stack[-1]+cur\n",
    "                    stack.pop()\n",
    "                stack.pop()\n",
    "                k=stack.pop()\n",
    "                cur=cur*k\n",
    "                stack.append(cur)\n",
    "                i+=1\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "                i+=1\n",
    "        for i in stack:\n",
    "            ans+=i\n",
    "        return ans\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s):\n",
    "        while '[' in s:\n",
    "            s = self.replaceOne(s)\n",
    "        return s\n",
    "\n",
    "    def replaceOne(self, s) -> str:\n",
    "        def getnew(matched):\n",
    "            return int(matched.group('num')) * matched.group('chr')\n",
    "\n",
    "        pat = re.compile(r'(?P<num>\\d+)\\[(?P<chr>[a-z]+)\\]', re.I)\n",
    "        return re.sub(pat, getnew, s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    " \n",
    "        stack,res, multi = [], \"\", 0\n",
    "\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res,multi = '',0\n",
    "            elif c == ']':\n",
    "                cur_multi, cur_res = stack.pop()\n",
    "                res = cur_res + cur_multi * res \n",
    "            elif '0' <= c <='9':\n",
    "                multi = multi * 10 + int(c)\n",
    "            else:\n",
    "                res += c\n",
    "                \n",
    "        return res \n",
    "\n",
    "        # stack, res, multi = [], \"\", 0\n",
    "        # for c in s:\n",
    "        #     if c == '[':\n",
    "        #         stack.append([multi, res])\n",
    "        #         res, multi = \"\", 0\n",
    "        #     elif c == ']':\n",
    "        #         cur_multi, last_res = stack.pop()\n",
    "        #         res = last_res + cur_multi * res\n",
    "        #     elif '0' <= c <= '9':\n",
    "        #         multi = multi * 10 + int(c)            \n",
    "        #     else:\n",
    "        #         res += c\n",
    "        # return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res , multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)\n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    #  递归未掌握\n",
    "    def decodeString0(self, s: str) -> str:\n",
    "        stack = []\n",
    "        n = len(s)\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            if s[i].isdigit():\n",
    "                for j in range(i + 1, n):\n",
    "                    if not s[j].isdigit():\n",
    "                        break\n",
    "                stack.append(int(s[i: j]))\n",
    "                i = j\n",
    "                continue\n",
    "            elif s[i] == '[':\n",
    "                stack.append(s[i])\n",
    "            elif s[i] == ']':\n",
    "                sub_s = ''\n",
    "                while True:\n",
    "                    ch = stack.pop()\n",
    "                    if ch == '[':\n",
    "                        break\n",
    "                    else:\n",
    "                        sub_s = ch + sub_s\n",
    "                sub_s *= stack.pop()\n",
    "                stack.append(sub_s)\n",
    "            else:\n",
    "                stack.append(s[i])\n",
    "            i += 1\n",
    "        return ''.join(stack)\n",
    "\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeString(self, s: str) -> str:\r\n",
    "        if len(s)<=2:\r\n",
    "            return s\r\n",
    "        \r\n",
    "        self.string = s\r\n",
    "        \r\n",
    "        res = self.decode(0, len(self.string)-1, 1)\r\n",
    "        return res\r\n",
    "            \r\n",
    "    def decode(self, left, right, rpt_time):\r\n",
    "        # print(left, right, rpt_time)\r\n",
    "        if left>right or right>=len(self.string):\r\n",
    "            return \"\"\r\n",
    "        \r\n",
    "        pam_stack = []\r\n",
    "        idx = left\r\n",
    "        \r\n",
    "        dec_str = \"\"\r\n",
    "        cur_tpr_str = \"\"\r\n",
    "        first_left = -100\r\n",
    "        \r\n",
    "        while idx<=right:\r\n",
    "            chr = self.string[idx]\r\n",
    "            if len(pam_stack) == 0:\r\n",
    "                if \"a\"<= chr <=\"z\":\r\n",
    "                    dec_str+=chr\r\n",
    "                elif chr==\"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "                    first_left = idx\r\n",
    "                elif chr.isdigit():\r\n",
    "                    cur_tpr_str+=chr\r\n",
    "            else:\r\n",
    "                if chr ==\"]\":\r\n",
    "                    pam_stack.pop()\r\n",
    "                    if len(pam_stack)==0:\r\n",
    "                        tmp_res = (dec_str+self.decode(first_left+1, idx-1, int(cur_tpr_str))+self.decode(idx+1, right, 1)) * rpt_time\r\n",
    "                        # print(left, right, rpt_time, tmp_res)\r\n",
    "                        return tmp_res\r\n",
    "                    \r\n",
    "                elif chr == \"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "            idx += 1\r\n",
    "        return dec_str*rpt_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def decodeString(self, s: str) -> str:\r\n",
    "        if len(s)<=2:\r\n",
    "            return s\r\n",
    "        \r\n",
    "        self.string = s\r\n",
    "        \r\n",
    "        res = self.decode(0, len(self.string)-1, 1)\r\n",
    "        return res\r\n",
    "            \r\n",
    "    def decode(self, left, right, rpt_time):\r\n",
    "        print(left, right, rpt_time)\r\n",
    "        if left>right or right>=len(self.string):\r\n",
    "            return \"\"\r\n",
    "        \r\n",
    "        pam_stack = []\r\n",
    "        idx = left\r\n",
    "        \r\n",
    "        dec_str = \"\"\r\n",
    "        cur_tpr_str = \"\"\r\n",
    "        first_left = -100\r\n",
    "        \r\n",
    "        while idx<=right:\r\n",
    "            chr = self.string[idx]\r\n",
    "            if len(pam_stack) == 0:\r\n",
    "                if \"a\"<= chr <=\"z\":\r\n",
    "                    dec_str+=chr\r\n",
    "                elif chr==\"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "                    first_left = idx\r\n",
    "                elif chr.isdigit():\r\n",
    "                    cur_tpr_str+=chr\r\n",
    "            else:\r\n",
    "                if chr ==\"]\":\r\n",
    "                    pam_stack.pop()\r\n",
    "                    if len(pam_stack)==0:\r\n",
    "                        tmp_res = (dec_str+self.decode(first_left+1, idx-1, int(cur_tpr_str))+self.decode(idx+1, right, 1)) * rpt_time\r\n",
    "                        print(left, right, rpt_time, tmp_res)\r\n",
    "                        return tmp_res\r\n",
    "                    \r\n",
    "                elif chr == \"[\":\r\n",
    "                    pam_stack.append(chr)\r\n",
    "            idx += 1\r\n",
    "        return dec_str*rpt_time"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Node:\n",
    "    def __init__(self, value):\n",
    "        self.value = value\n",
    "        self.next = None\n",
    "        self.prev = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = Node(None)\n",
    "        self.tail = Node(None)\n",
    "        self.stack = []\n",
    "        self.stackTop = -1\n",
    "\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        self.toList(s)\n",
    "\n",
    "        while self.stackTop >= 0:\n",
    "            startNode = self.stack[self.stackTop][0]\n",
    "            endNode = self.stack[self.stackTop][1]\n",
    "            self.stackTop -= 1\n",
    "        \n",
    "            p = startNode.next\n",
    "            one = \"\"\n",
    "            while p != endNode:\n",
    "                one += p.value\n",
    "                p = p.next\n",
    "            repeatNode = startNode.prev\n",
    "            tmp = \"\"\n",
    "            for i in range(0, repeatNode.value):\n",
    "                tmp += one\n",
    "\n",
    "            repeatNode.next = endNode.next\n",
    "            endNode.next.prev = repeatNode\n",
    "            repeatNode.value = tmp\n",
    "            \n",
    "        result = \"\"\n",
    "        p = self.head.next\n",
    "        while p != self.tail:\n",
    "            result += p.value\n",
    "            p = p.next\n",
    "        return result\n",
    "\n",
    "    def toList(self, s):\n",
    "        current = self.head\n",
    "        for i in range(0, len(s)):\n",
    "            if type(current.value) == int and self.isInt(s[i]):\n",
    "                current.value = 10 * current.value + int(s[i])\n",
    "                continue\n",
    "                \n",
    "            pre = current\n",
    "            current = Node(s[i])\n",
    "            if (self.isInt(current.value)):\n",
    "                current.value = int(current.value)\n",
    "            if (self.head.next == None):\n",
    "                self.head.next = current\n",
    "            if s[i] == '[':\n",
    "                self.stackTop += 1\n",
    "                self.stack.append([current, None])\n",
    "            if s[i] == ']':\n",
    "                t = self.stackTop\n",
    "                while self.stack[t][1] != None:\n",
    "                    t -= 1\n",
    "                self.stack[t][1] = current\n",
    "                    \n",
    "            pre.next = current\n",
    "            current.prev = pre\n",
    "        current.next = self.tail\n",
    "        self.tail.prev = current\n",
    "\n",
    "    def isInt(self, ss):\n",
    "        return ord('0') <= ord(ss) and ord(ss) <= ord('9')\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        # stack=[]\n",
    "        # res=''\n",
    "        # mutil=0\n",
    "        # for c in s:\n",
    "        #     if c=='[':\n",
    "        #         stack.append([mutil,res])\n",
    "        #         res=''\n",
    "        #         mutil=0\n",
    "        #     elif c==']':\n",
    "        #         cur_multi,last_res=stack.pop()\n",
    "        #         res=last_res+cur_multi*res\n",
    "        #     elif '0'<=c <='9':\n",
    "        #         mutil=mutil*10+int(c)\n",
    "        #     else:\n",
    "        #         res+=c\n",
    "        # return res\n",
    "        stack,res,multi=[],'',0\n",
    "        for c in s :\n",
    "            if c=='[':\n",
    "                stack.append([multi,res])\n",
    "                res,multi='',0\n",
    "            elif c==']':\n",
    "                hidmulti,last_res=stack.pop()\n",
    "                res=last_res+hidmulti*res\n",
    "            elif '0'<=c<='9':\n",
    "                multi=multi*10+int(c)\n",
    "            else:\n",
    "                res+=c\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    start_point=0\n",
    "\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        if(self.start_point==len(s)):\n",
    "            return ''\n",
    "        while(True):\n",
    "            c=s[self.start_point]\n",
    "            if (c.isdigit()):\n",
    "                digit=self.getDigit(s[self.start_point:])\n",
    "                string1 = digit*self.decodeString(s)\n",
    "                return string1+self.decodeString(s)\n",
    "            else:\n",
    "                self.start_point += 1\n",
    "                if(c == '['):\n",
    "                    return self.decodeString(s)\n",
    "                elif(c == ']'):\n",
    "                    return ''\n",
    "                else:\n",
    "                    # c is a letter\n",
    "                    return c+self.decodeString(s)\n",
    "    \n",
    "    def getDigit(self, s: str) -> int:\n",
    "        result=''\n",
    "        for c in s:\n",
    "            if (c.isdigit()):\n",
    "                self.start_point+=1\n",
    "                result += c\n",
    "            else:\n",
    "                break\n",
    "        return int(result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def decodeString(self, s: str) -> str:\n",
    "        stack, res, multi = [], \"\", 0\n",
    "        for c in s:\n",
    "            if c == '[':\n",
    "                stack.append([multi, res])\n",
    "                res, multi = \"\", 0\n",
    "            elif c == ']':\n",
    "                cur_multi, last_res = stack.pop()\n",
    "                res = last_res + cur_multi * res\n",
    "            elif '0' <= c <= '9':\n",
    "                multi = multi * 10 + int(c)            \n",
    "            else:\n",
    "                res += c\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
